package net.tp.algo.topic;

import java.awt.Color;
import java.awt.Component;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.awt.image.BufferedImage;
import java.io.IOException;
import java.util.Arrays;

import javax.swing.JFrame;

import net.tp.fractal.Mandelbrot;

/**
 * 
 * <p>Apply shortest path algorithm for DAG.<p>
 * 
 * 
 * <p>Shortest Path for DAG algorithm: do topological sorting for DAG, then for each node $u$ in the topological sorting order,
 * relax every edges u-w.</p>
 * 
 * @author Trung Phan
 *
 */
public class SeamCarver {

	private final static int BORDER_ENERGY = 255 * 255 + 255 * 255 + 255 * 255;

	private int[][] color;
	private double[][] energy;

	private boolean transpose;

	public SeamCarver(BufferedImage image) {
		int w = image.getWidth();
		int h = image.getHeight();

		color = new int[w][h];
		energy = new double[w][h];

		for (int x = 0; x < w; x++) {
			for (int y = 0; y < h; y++) {
				color[x][y] = image.getRGB(x, y);
			}
		}
		for (int x = 0; x < w; x++) {
			for (int y = 0; y < h; y++) {
				energy[x][y] = _energy(x, y);
			}
		}

	}

	/**
	 * Create picture
	 * 
	 * @return image
	 */
	public BufferedImage image() {

		transpose(false);
		
		int w = color.length;
		int h = w > 0 ? color[0].length : 0;

		BufferedImage newPicture = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
		for (int x = 0; x < w; x++) {
			for (int y = 0; y < h; y++) {
				newPicture.setRGB(x, y, color[x][y]);
			}
		}

		return newPicture;
	}

	/**
	 * <p>One way to defining energy function: energy for pixel (x,y)<p>
	 * @param x x coordinate
	 * @param y y coordinate
	 * @return energy at pixel(x,y)
	 */
	public double energy(int x, int y) {
		if (transpose) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		return _energy(x, y);
	}

	/**
	 * sequence of indices for horizontal seam
	 * @return y coordinates of horizontal seam
	 */
	public int[] findHorizontalSeam() {
		transpose(true);
		return _findVerticalSeam();
	}

	/**
	 * Sequence of indices for vertical seam
	 * 
	 * @return x coordinates of vertical seam
	 */
	public int[] findVerticalSeam() {
		transpose(false);
		return _findVerticalSeam();
	}

	/**
	 * remove horizontal seam from picture
	 * @param a y coordinates of horizontal seam
	 */
	public void removeHorizontalSeam(int[] a) {
		transpose(true);
		_removeVerticalSeam(a);
	}

	/**
	 * remove vertical seam from picture
	 * @param a x coordinates of vertical seam
	 */
	public void removeVerticalSeam(int[] a) {
		transpose(false);
		_removeVerticalSeam(a);
	}

	private void rotate() {

		// new width = old height;
		int w = color.length > 0 ? color[0].length : 0;
		
		// new height = old width
		int h = color.length;

		int[][] newColor = new int[w][h];
		double[][] newEnergy = new double[w][h];

		for (int x = 0; x < w; x++) {
			for (int y = 0; y < h; y++) {
				newColor[x][y] = color[y][x];
				newEnergy[x][y] = energy[y][x];
			}
		}
		color = newColor;
		energy = newEnergy;
		transpose = !transpose;
	}

	private void transpose(boolean on) {
		if (transpose != on) {
			rotate();
		}
	}

	/**
	 * Width of current picture
	 * 
	 * @return picture width
	 */
	public int width() {
		int w = color.length;
		int h = w > 0 ? color[0].length : 0;
		return !transpose ? w : h;
	}

	/**
	 * Height of current picture
	 * 
	 * @return picture height
	 */
	public int height() {
		int w = color.length;
		int h = w > 0 ? color[0].length : 0;
		return !transpose ? h : w;
	}

	/**
	 * Energy of pixel at column x and row y
	 * 
	 * @param x x coordinate
	 * @param y y coordinate
	 * @return energy at pixel(x,y)
	 */
	private double _energy(int x, int y) {

		int w = color.length;
		int h = w > 0 ? color[0].length : 0;

		if (x < 0 || x >= w || y < 0 || y >= h) {
			throw new IndexOutOfBoundsException();
		}

		if (x == 0 || x == w - 1 || y == 0 || y == h - 1) {
			return BORDER_ENERGY;
		}

		Color left = new Color(color[x - 1][y]);
		Color right = new Color(color[x + 1][y]);
		Color top = new Color(color[x][y - 1]);
		Color bottom = new Color(color[x][y + 1]);

		int Rx = left.getRed() - right.getRed();
		int Gx = left.getGreen() - right.getGreen();
		int Bx = left.getBlue() - right.getBlue();
		int Ry = top.getRed() - bottom.getRed();
		int Gy = top.getGreen() - bottom.getGreen();
		int By = top.getBlue() - bottom.getBlue();
		return Rx * Rx + Gx * Gx + Bx * Bx + Ry * Ry + Gy * Gy + By * By;
	}

	/**
	 * Sequence of indices for vertical seam
	 * 
	 * @return x coordinates of vertical seam
	 */
	private int[] _findVerticalSeam() {

		int w = color.length;
		int h = w > 0 ? color[0].length : 0;

		double[][] distTo = new double[w][h];
		int[][] edgeTo = new int[w][h];

		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				_updateDistance(x, y, distTo, edgeTo);
			}
		}

		double shortestDistance = Double.MAX_VALUE;
		int shortestY = 0;
		for (int x = 0; x < w; x++) {
			if (shortestDistance > distTo[x][h - 1]) {
				shortestDistance = distTo[x][h - 1];
				shortestY = x;
			}
		}

		int[] result = new int[h];

		for (int y = h - 1; y >= 0; y--) {
			result[y] = shortestY;
			shortestY = edgeTo[shortestY][y];
		}

		return result;
	}

	private void _updateDistance(int x, int y, double[][] distTo,
			int[][] edgeTo) {

		int w = color.length;

		double distance = Double.MAX_VALUE;

		if (y == 0) {
			distance = 0;
			edgeTo[x][y] = -1;
		} else {
			if (distance > distTo[x][y - 1]) {
				distance = distTo[x][y - 1];
				edgeTo[x][y] = x;
			}
			if (x > 0 && distance > distTo[x - 1][y - 1]) {
				distance = distTo[x - 1][y - 1];
				edgeTo[x][y] = x - 1;
			}
			if (x < w - 1 && distance > distTo[x + 1][y - 1]) {
				distance = distTo[x + 1][y - 1];
				edgeTo[x][y] = x + 1;
			}
		}

		distance += energy[x][y];

		distTo[x][y] = distance;
	}

	/**
	 * Remove Vertical Seam
	 * 
	 * @param a x coordinates of vertical seam
	 */
	private void _removeVerticalSeam(int[] a) {

		int w = color.length;
		int h = w > 0 ? color[0].length : 0;

		if (a.length != h) {
			throw new IllegalArgumentException();
		}
		// doing validation first
		for (int y = 0; y < h; y++) {
			if (a[y] < 0 || a[y] >= w) {
				throw new IllegalArgumentException();
			}
		}

		if (w <= 1) {
			color = new int[0][0];
			energy = new double[0][0];
		} else {
			for (int y = 0; y < h; y++) {
				for (int x = a[y]; x < w - 1; x++) {
					color[x][y] = color[x + 1][y];
					energy[x][y] = energy[x + 1][y];
				}
			}

			w--;
			color = Arrays.copyOf(color, w);
			energy = Arrays.copyOf(energy, w);
		}

		// update energy of cells around the removed vertical seams
		for (int y = 0; y < h; y++) {
			int x = a[y];
			for (int _x = x-1; _x <= x+1; _x++) {
				for (int _y = y-1; _y <= y+1; _y++) {
					if (_x >= 0 && _x < w && _y >= 0 && _y < h) {
						energy[_x][_y] = _energy(_x, _y);
					}
				}
			}
		}

	}
	
	
	public static void main(String ... args) throws IOException {

		System.out.print("Generating fractal image... ");
		final BufferedImage image = Mandelbrot.generate(500, 0.1015, -0.633, 0.01);
		System.out.println("Done.");
		
		JFrame f = new JFrame("Image - Resize Me");
        
        f.addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });
        
        f.add(new ImageWindow(image));
        
        f.pack();
        f.setVisible(true);
	}
	
	@SuppressWarnings("serial")
	private static class ImageWindow extends Component {
		
		private BufferedImage image;
		private SeamCarver seamCarver;
		
		public ImageWindow(BufferedImage image) {
			this.image = image;
			this.seamCarver = new SeamCarver(image);
		}
    	@Override
	    public void paint(Graphics g) {
    		
    		if (image.getWidth() <= this.getWidth() && image.getHeight() <= this.getHeight()) {
    	        g.drawImage(image, 0, 0, null);
    		}
    		else {
    			if (seamCarver.width() < this.getWidth() || seamCarver.height() < this.getHeight()) {
    				seamCarver = new SeamCarver(image);
    			}
				int columns = seamCarver.width() - this.getWidth();
				int rows = seamCarver.height() - this.getHeight();
				for (int i = 0; i < columns; i++) {
					int[] seam = seamCarver.findVerticalSeam();
					seamCarver.removeVerticalSeam(seam);
				}
				for (int i = 0; i < rows; i++) {
					int[] seam = seamCarver.findHorizontalSeam();
					seamCarver.removeHorizontalSeam(seam);
				}
    			
    	        g.drawImage(seamCarver.image(), 0, 0, null);
    		}    		
	    }
    	
    	@Override
	    public Dimension getPreferredSize() {
	        return new Dimension(image.getWidth(), image.getHeight());
    	}
	}
	
}
